
// Forward Declaration
template <int inst>
class __malloc_alloc_template;

template <bool threads, int inst>
class __default_alloc_template;

// Whether use multi-thread allocator
#define __NODE_ALLOCATOR_THREADS false

// --------------------------------------------- //
// hamster_allocator -> allocate and deallocate
// No Use For Now
using malloc_alloc = __malloc_alloc_template<0>;
#ifdef __USE_MALLOC
using alloc = malloc_alloc;
#else
using alloc = __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0>;
#endif

#if 0
#include <new>
#elif !defined(__THROW_BAD_ALLOC)
#include <iostream>
#define __THROW_BAD_ALLOC                      \
    std::cerr << "out of memory" << std::endl; \
    exit(1);
#endif

// First Layer of allocator
template <int inst>
class __malloc_alloc_template
{
private:
    // To process when malloc is return 0 (memory is not enough)
    // function declaration
    static void *oom_malloc(std::size_t);
    // function declaration
    static void *oom_realloc(void *, std::size_t);
    // function pointer declaration
    static void (*__malloc_alloc_oom_handler)();

public:
    static void *allocate(std::size_t n)
    {
        void *result = malloc(n);
        if (result == 0)
        {
            result = oom_malloc(n);
        }
        return result;
    }

    static void deallocate(void *p, std::size_t)
    {
        free(p);
    }

    static void *reallocate(void *p, std::size_t old_size, std::size_t new_size)
    {
        void *result = realloc(p, new_size);
        if (result == 0)
        {
            result = oom_realloc(p, new_size);
        }
        return result;
    }

    // set oom handler and return old handler
    static void (*set_malloc_handler(void (*f)()))()
    {
        void (*old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return old;
    }
};

void out_of_memory()
{
    std::cerr << "Memory allocation failed. Terminating program." << std::endl;
    exit(1);
}

// default oom handler
template <int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = out_of_memory;

template <int inst>
void *__malloc_alloc_template<inst>::oom_malloc(std::size_t n)
{
    void (*my_malloc_handler)();
    void *result;

    for (;;)
    {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (my_malloc_handler == nullptr)
            __THROW_BAD_ALLOC;
        (*my_malloc_handler)();
        result = malloc(n);
        if (result != nullptr)
            return result;
    }
}

template <int inst>
void *__malloc_alloc_template<inst>::oom_realloc(void *p, std::size_t n)
{
    void (*my_malloc_handler)();
    void *result;

    for (;;)
    {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (my_malloc_handler == nullptr)
            __THROW_BAD_ALLOC;
        (*my_malloc_handler)();
        result = realloc(p, n);
        if (result != nullptr)
            return result;
    }
}

// --------------------------------------------- //
// SGI ---- Layer two Allocator
enum
{
    __ALIGN = 8
};
enum
{
    __MAX_BYTES = 128
};
enum
{
    __NFREELISTS = __MAX_BYTES / __ALIGN
};

template <bool threads, int inst>
class __default_alloc_template
{
private:
    static std::size_t round_up(size_t bytes)
    {
        return ((bytes + __ALIGN - 1) & ~(__ALIGN - 1));
    }

private:
    union obj
    {
        union obj *free_list_link;
        char client_data[1];
    };

private:
    static obj *volatile Free_List[__NFREELISTS];
    static std::size_t FREELIST_INDEX(size_t bytes)
    {
        return ((bytes + __ALIGN - 1) / __ALIGN - 1);
    }

    static void *refill(std::size_t n);

    static char *chunk_alloc(std::size_t n, int &nobjs);

    // Chunk allocation state
    static char *start_free;
    static char *end_free;
    static std::size_t heap_size;

public:
    static void *allocate(std::size_t n)
    {
        obj *volatile *my_free_list;
        obj *result;
        if (n > static_cast<std::size_t>(__MAX_BYTES))
        {
            // size > 128 bytes -> call layer 1 allocator
            return malloc_alloc::allocate(n);
        }

        // find 16 free-list most appropriate one
        // pointer array -> Free_List -> type is pointer of pointer of obj
        my_free_list = Free_List + FREELIST_INDEX(n);
        result = *my_free_list;
        if (result == nullptr)
        {
            // No Find appropriate free-list -> call refill
            return refill(round_up(n));
        }
        // Find Appropriate free-list
        *my_free_list = result->free_list_link;
        return result;
    }

    static void deallocate(void *p, std::size_t n)
    {
        obj *q = static_cast<obj *>(p);
        obj *volatile *my_free_list;
        if (n > static_cast<std::size_t>(__MAX_BYTES))
        {
            malloc_alloc::deallocate(p, n);
            return;
        }

        my_free_list = Free_List + FREELIST_INDEX(n);
        q->free_list_link = *my_free_list;
        *my_free_list = q;
    }

    static void *reallocate(void *p, std::size_t old_size, std::size_t new_size);
};

template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free = nullptr;

template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = nullptr;

template <bool threads, int inst>
std::size_t __default_alloc_template<threads, inst>::heap_size = 0;

template <bool threads, int inst>
typename __default_alloc_template<threads, inst>::obj *volatile __default_alloc_template<threads, inst>::Free_List[__NFREELISTS] = {0};

template <bool threads, int inst>
void *__default_alloc_template<threads, inst>::refill(std::size_t n)
{
    // Assum n(bytes) is 8 bytes aligned
    // return a n bytes blocks
    // nobjs means how many blocks, every blocks size is n
    int nobjs = 20;
    obj *volatile *my_free_list;
    char *chunk = chunk_alloc(n, nobjs);

    obj *result;
    obj *current_obj, next_obj;
    int i;

    // Only one new blocks
    if (nobjs == 1)
        return chunk;
    // nobjs > 1 -> adjust the free list
    my_free_list = Free_List + FREELIST_INDEX(n);

    // In chunk space to build free_list
    // result return to user
    result = reinterpret_cast<obj *>(chunk);
    // adjust the free_list
    *my_free_list = next_obj = reinterpret_cast<obj *>(chunk + n);
    for (int i = 1;; i++)
    {
        current_obj = next_obj;
        next_obj = reinterpret_cast<obj *>(static_cast<char *>(next_obj) + n);
        if (nobjs - 1 == i)
        {
            // the last block's(union) free_list_link = 0
            current_obj->free_list_link = 0;
            break;
        }
        else
        {
            // To Form a Link-List
            current_obj->free_list_link = next_obj;
        }
    }
    return result;
}

template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::chunk_alloc(std::size_t size, int &nobjs)
{
    char *result;
    size_t total_bytes = size * nobjs;
    size_t bytes_left = end_free - start_free;

    if (bytes_left >= total_bytes)
    {
        // left memory is enough
        result = start_free;
        start_free += total_bytes;
        return result;
    }
    else if (bytes_left >= size)
    {
        // left memory is not enough, but enough to build a new block contains at least one objs
        nobjs = bytes_left / size;
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;
        return result;
    }
    else
    {
        size_t bytes_to_get = 2 * total_bytes + round_up(heap_size >> 4);
        if (bytes_left > 0)
        {
            // memory space is little enough
            // assign memory to suitable block
            obj *volatile *my_free_list = Free_List + FREELIST_INDEX(bytes_left);
            // adjust the this free_list
            static_cast<obj *>(start_free)->free_list_link = *my_free_list;
            *my_free_list = static_cast<obj *>(start_free);
        }

        // get memory from heap
        start_free = (char *)malloc(bytes_to_get);
        if (start_free == 0)
        {
            // malloc fail
            obj *volatile *my_free_list, *p;
            for (int i = size; i <= __MAX_BYTES; i += __ALIGN)
            {
                my_free_list = Free_List + FREELIST_INDEX(i);
                p = *my_free_list;
                // free_list is not full use by other thread
                // this free_list inside has not use block
                if (p != 0)
                {
                    *my_free_list = p->free_list_link;
                    start_free = (char *)p;
                    end_free = start_free + i;
                    return (char *)chunk_alloc(size, nobjs);
                }
            }
            end_free = 0;
            start_free = (char *)malloc_alloc::allocate(bytes_to_get);
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;
        return (char *)chunk_alloc(size, nobjs);
    }
}
